package data_structure.mooc;
import data_structure.helper.ArrayGenerator;
import data_structure.helper.SortingHelper;

import java.util.Arrays;
import static data_structure.helper.SwapArray.swap;


public class HeapSort {

    private HeapSort() {

    }

    public static <E extends Comparable<E>> void sort(E []arr){
        //预处理判断
        if(arr.length==1){
            return;
        }
        //将数组调整为最大堆，从数组最后一个元素的父节点开始，直到数组中第一个元素，进行siftDown操作
        for(int i=(arr.length-1-1)/2;i>=0;i--){
            siftDown(arr,i,arr.length);
        }
        //原地排序，每次将数组中第一个元素和数组“尾部元素”交换，进行siftDown操作，最终得到结果
        for(int i=arr.length - 1; i >= 0; i--){
            swap(arr,0,i);
            siftDown(arr,0,i);
        }
    }

    /**
     * 用来处理父亲节点和左孩子，右孩子之间的关系，调整为最大堆
     * @param arr
     * @param k
     * @param length 完全二叉树中元素的个数可以改变
     * @param <E>
     */
    private static<E extends Comparable<E>> void siftDown(E[]arr,int k,int length){
        //从当前位置（k）开始，遍历当前位置的左孩子，直到二叉树的末尾
        while(k*2+1<length){
            //找到左右子树的最大值
            int i=k*2+1;
            int j=i+1;
            if(j<length&&arr[j].compareTo (arr[i])>0){
                i=j;
            }
            //符合要求时，跳出循环
            if(arr[k].compareTo (arr[i])>0)break;
            //交换元素
            swap(arr,k,i);
            k=i;
        }

    }

    public static void main(String[] args) {
        Integer[]arr = ArrayGenerator.generateNormalArray (1000000,1000000);
        Integer[]arr1 = Arrays.copyOf(arr, arr.length);
        SortingHelper.testSorting (arr,"heapSort");
        SortingHelper.testSorting (arr1,"quickSort");
    }

}
